class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
list_a = [1,2,3,4,5]
def input_data(a,headnode):
    headnode.data = a[0]
    pre = headnode
    for data in a[1:]:
        node = Node(0)
        node.data = data
        pre.next = node
        pre = pre.next
    return headnode
def output_data(headnode):
    while(headnode is not None):
        print(headnode.data)
        headnode = headnode.next

head = Node(0)
head = input_data(list_a,head)
output_data(head)
#链表反转
list_b = [1,2,3,4,5]
def reverse_list(head):
    prev = Node(0)
    cur =  Node(0)
    cur = head
    head = head.next
    prev = head
    cur.next = None
    while head.next is not None:
        head = head.next
        prev.next = cur
        cur = prev
        prev = head
    prev.next = cur
    cur = prev
    return cur
head_b = Node(0)
headnode_b = input_data(list_b,head_b)
output_node_b = reverse_list(headnode_b)
output_data(output_node_b)

#环形链表检测
start_node = Node(0)
middle_node1 = Node(1)
middle_node2 = Node(2)
last_node = start_node
# last_node = Node(4)
start_node.next = middle_node1
middle_node1.next = middle_node2
middle_node2.next = last_node
head = start_node
while(head.next is not None):
    flag=False
    if "app" not in str(head.data):
        head.data = str(head.data)
        head.data += "app"
        head = head.next
    else:
        flag=True
        print("true")
        break;
if flag == False:
    print("false")

#合并两个有序链表
list_ax = [1,2,3,4,5]
list_bx = [2,4,6,8,10]
head_ax = Node(0)
head_ax = input_data(list_ax,head_ax)
output_data(head_ax)
head_bx = Node(0)
head_bx = input_data(list_bx,head_bx)
output_data(head_bx)
def plus_list(head_ax,head_bx):
    head_cx = Node(0)
    headx = head_cx
    head_cx.data = head_ax.data if head_ax.data < head_bx.data else head_b.data
    while(head_ax and head_bx):
        if head_ax.data < head_bx.data:
            node_c = Node(0)
            node_c.data = head_ax.data
            headx.next = node_c
            headx = headx.next
            head_ax = head_ax.next
        else:
            node_c = Node(0)
            node_c.data = head_bx.data
            headx.next = node_c
            headx = headx.next
            head_bx = head_bx.next
        print("node_c.data="+str(node_c.data))

    while(headx is not None):
        print("headx")
        if (head_ax is not None):
            node_c = Node(0)
            node_c.data = head_ax.data
            headx.next = node_c
            headx = headx.next
            head_ax = head_ax.next
            if head_ax is None:
                break
        elif(head_bx is not None):
            node_c = Node(0)
            node_c.data = head_bx.data
            headx.next = node_c
            headx = headx.next
            head_bx = head_bx.next
            if head_bx is None:
                break
    return head_cx
head_dx = plus_list(head_ax,head_bx)
print("output:")
output_data(head_dx)

#双向链表操作，双向循环链表
class BothNodes:
    def __init__(self,data):
        self.pre = None
        self.next = None
        self.data = data

double_linklist = [1,2,3,4,5,6,7,8,9,10]
def input(linklist_a):
    head = BothNodes(0)
    head.data = linklist_a[0]
    tail = BothNodes(0)
    prev = head
    for data in linklist_a[1:]:
        newnode = BothNodes(data)
        prev.next = newnode
        newnode.pre = prev
        prev = newnode
    tail = prev
    tail.next = head
    return head,tail
def output(head,tail):
    while head is not tail:
        print(head.data)
        head = head.next
    print(tail.data)
head,tail = input(double_linklist)
print("double linklist output:")
output(head,tail)
def add(head,tail,data):
    newnode = BothNodes(data)
    back = head.next
    head.next = newnode
    newnode.pre = head
    newnode.next = back
    back.pre = head
    return head,tail
def delete(head,tail,data):
    prev = head
    delete_node = head.next
    if prev.data == data:
        delete_node = prev
        prev = tail
    while prev is not tail:
         if delete_node.data == data:
             break
         else:
             prev = prev.next
             delete_node = delete_node.next
    back = delete_node.next
    prev.next = back
    back.pre = prev
    return head,tail
def put(head,tail,data):
    #修改指定data。
    delete_node = head.next
    if head.data == data:
        head.data = "data3"
    while delete_node is not tail:
        if delete_node.data == data:
            delete_node.data = "data3"
        else:
            delete_node = delete_node.next
    return head,tail
def check(head,tail,data):
    #查找指定data返回prev和next的数据。
    prev = head
    check_node = head.next
    if prev.data == data:
        check_node = prev
        prev = tail
    while prev is not tail:
        if check_node.data == data:
            break
        else:
            prev = prev.next
            check_node = check_node.next
    back = check_node.next
    return head, tail,"prev="+str(prev.data)+"back"+str(back.data)
add(head,tail,data="data1")
output(head,tail)
delete(head,tail,data=2)
output(head,tail)
put(head,tail,data=4)
output(head,tail)
head,tail,output_str=check(head,tail,data=7)
output(head,tail)
print(output_str)
#增删改查